Computational complexity is examined using the principle of increasing entropy. To consider computation as a physical process\r\nfrom an initial instance to the final acceptance is motivated because information requires physical representations and because\r\nmany natural processes complete in nondeterministic polynomial time (NP). The irreversible process with three or more degrees of\r\nfreedom is found intractable when, in terms of physics, flows of energy are inseparable from their driving forces. In computational\r\nterms, when solving a problem in the class NP, decisions among alternatives will affect subsequently available sets of decisions.\r\nThus the state space of a nondeterministic finite automaton is evolving due to the computation itself, hence it cannot be efficiently\r\ncontracted using a deterministic finite automaton. Conversely when solving problems in the class P, the set of states does not\r\ndepend on computational history, hence it can be efficiently contracted to the accepting state by a deterministic sequence of\r\ndissipative transformations. Thus it is concluded that the state set of class P is inherently smaller than the state set of class NP.\r\nSince the computational time needed to contract a given set is proportional to dissipation, the computational complexity class P\r\nis a proper (strict) subset of NP.
Loading....